package com.peng.leetcode.dfs;

/**
 * FindCircleNum
 *
 * 547. 省份数量
 *
 * @author: lupeng6
 * @create: 2021/1/7 14:07
 */
public class FindCircleNum {

    public static void main(String[] args) {
        int[][] isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
//        int circleNum = new FindCircleNum().findCircleNum(isConnected);
//        System.out.println(circleNum);

        new Solution().findCircleNum(isConnected);
    }

//    public int findCircleNum(int[][] isConnected) {
//        if (isConnected.length == 0) {
//            return 0;
//        }
//        int m = isConnected.length;
//        boolean[] visited = new boolean[m];
//        Queue<Integer> queue = new LinkedList<>();
//        int sum = 0;
//        for (int i = 0; i < isConnected.length; i++) {
//            if (!visited[i]) {
//                queue.offer(i);
//                while (!queue.isEmpty()) {
//                    Integer poll = queue.poll();
//                    int[] ints = isConnected[poll];
//                    visited[poll] = true;
//                    for (int j = 0; j < ints.length; j++) {
//                        int next = ints[j];
//                        if (next == 1 && !visited[j]) {
//                            queue.offer(j);
//                        }
//                    }
//                }
//                sum++;
//            }
//        }
//        return sum;
//    }

    private boolean[] visited;

    public int findCircleNum(int[][] isConnected) {
        if (isConnected.length == 0) {
            return 0;
        }
        int sum = 0;
        this.visited = new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            if (!visited[i]) {
                dfs(isConnected, i);
                sum++;
            }
        }
        return sum;
    }

    public void dfs(int[][] isConnected, int x) {
        if (visited[x]) {
            return;
        }
        int[] ints = isConnected[x];
        visited[x] = true;
        for (int i = 0; i < ints.length; i++) {
            int anInt = ints[i];
            if (anInt == 1) {
                dfs(isConnected, i);
            }
        }
    }

    /**
     * 并查集
     *
     * @author lupeng6
     * @date 2021/1/11 15:35
     */
    static class Solution {

        private int[] parent;

        public int findCircleNum(int[][] isConnected) {
            int provinces = isConnected.length;
            parent = new int[provinces];
            for (int i = 0; i < provinces; i++) {
                parent[i] = i;
            }
            for (int i = 0; i < provinces; i++) {
                for (int j = i + 1; j < provinces; j++) {
                    if (isConnected[i][j] == 1) {
                        union(i, j);
                    }
                }
            }
            int circles = 0;
            for (int i = 0; i < provinces; i++) {
                if (parent[i] == i) {
                    circles++;
                }
            }
            return circles;
        }

        public void union(int index1, int index2) {
            int i = find(index1);
            int j = find(index2);
            parent[i] = j;
        }

        public int find(int index) {
            if (parent[index] != index) {
                parent[index] = find(parent[index]);
            }
            return parent[index];
        }
    }
}
